并查集——数据结构系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

并查集（又称不相交集合 Disjoint Set Union，DSU）是一种高效处理动态连通性问题的树形数据结构，核心支持查找元素所属集合和合并两个不相交集合操作，经过路径压缩和按秩 / 大小合并优化后，操作均摊时间复杂度接近 O(1)，是图论、贪心算法等领域的常用工具, 广泛应用于图的连通性判断、最小生成树（Kruskal 算法）、分组问题等场景。本文将详细讲解并查集的原理与实现，内容由浅入深，所有代码可直接编译运行。

图结构的实现方式：

邻接矩阵图：是一种使用「一维数组 + 二维数组」存储顶点和边数据的图结构，稠密图中常被采用；
邻接链表图：是一种使用「数组 + 链表」存储顶点和边数据的图结构，稀疏图中常被采用；

学习经典应用场景前，请根据上面的教程封装好自定义图，所有场景实例直接复用

教程目录导航

▼

连通性问题

一、核心概念

1.1 基本思想

用树形结构表示每个集合，每个集合有一个根节点（代表元），集合内所有元素最终都指向根节点：

同一集合的元素共享同一个根节点；
不同集合的根节点不同；
查找操作：找到元素的根节点，确定所属集合；
合并操作：将一个集合的根节点指向另一个集合的根节点，合并两个树形结构。

1.2 核心优化

并查集的原始实现会出现树退化成链表的情况，需通过两种优化将时间复杂度降至均摊 O(α(n))，α(n) 为阿克曼函数的反函数，增长极慢，n<10⁶⁰⁰ 时 α(n)≤5，可认为是常数）。

路径压缩（Find 操作优化）
- 查找元素根节点时，将查找路径上的所有节点直接指向根节点，扁平化树形结构，避免后续查找重复遍历路径。
按秩合并（Union 操作优化）
- "秩” 通常表示树的高度（也可用集合大小），合并时将秩更小的树的根节点指向秩更大的树的根节点，保证树的高度尽可能小，避免形成深树。

二、核心操作

并查集的实现围绕父节点数组和秩数组展开，先定义两个基础数组：

parent[]：parent[x] 表示元素 x 的父节点，初始时 parent[x] = x（每个元素自成一个集合，根节点是自己）；
rank[]：rank[x] 表示以 x 为根的树的高度，初始时 rank[x] = 1（单个元素的树高度为 1）。

2.1 查找（Find）—— 带路径压缩

找到元素 x 所属集合的根节点，同时压缩查找路径。


//递归版（简洁，适合理解，数据量大时可能栈溢出）
int find(int x) {
    // 递归终止：根节点的父节点是自己
    if (parent[x] != x) {
        // 路径压缩：将x的父节点直接指向根节点
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

//迭代版（推荐，无栈溢出风险，效率更高）：
int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 路径压缩：将查找路径上所有节点直接指向根节点
    while (parent[x] != root) {
        int next = parent[x]; // 保存x的原父节点
        parent[x] = root;     // x直接指向根节点
        x = next;             // 继续处理原父节点
    }
    return root;
}

2.2 合并（Union）—— 按秩合并

将元素 x 和 y 所在的两个集合合并为一个集合。

分别找到 x 和 y 的根节点 rootX、rootY；
若 rootX == rootY，说明已在同一集合，无需合并；
若 rootX != rootY，按秩合并：将秩小的树指向秩大的树，若秩相等，合并后根节点的秩 + 1。


void unite(int x, int y) {
    x = find(x); // 找到x的根
    y = find(y); // 找到y的根
    if (x == y) return; // 同一集合，直接返回
    // 按秩合并：小秩树指向大秩树
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        // 秩相等时，合并后根节点秩+1
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

2.3 判断连通（Same）

判断元素 x 和 y 是否属于同一个集合（即是否连通）。

只需判断两者的根节点是否相同。


bool same(int x, int y) {
    return find(x) == find(y);
}

三、无向图连通性---并查集

通过两次 DFS 实现强连通分量的查找。

算法解析：

对原图进行 DFS，记录顶点的后序遍历顺序，并按后序时间从晚到早排序。
将原图的所有边反向，得到逆图。
按照第一步得到的顺序，对逆图进行 DFS，每一次遍历得到的顶点集合就是一个强连通分量。


#include <iostream>
#include <vector>
#include"ArrayGraph.h"

using namespace std;

vector<int> parent; // 父节点数组
vector<int> ranks;   // 秩数组（树的高度）

// 查找：带路径压缩
int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 路径压缩：将查找路径上所有节点直接指向根节点
    while (parent[x] != root) {
        int next = parent[x]; // 保存x的原父节点
        parent[x] = root;     // x直接指向根节点
        x = next;             // 继续处理原父节点
    }
    return root;
}

// 合并：按秩合并
void unite(int x, int y) {
    x = find(x); // 找到x的根
    y = find(y); // 找到y的根
    if (x == y) return; // 同一集合，直接返回
    // 按秩合并：小秩树指向大秩树
    if (ranks[x] < ranks[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        // 秩相等时，合并后根节点秩+1
        if (ranks[x] == ranks[y]) {
            ranks[x]++;
        }
    }
}

// 判断是否连通：同一集合返回true
bool same(int x, int y) {
    return find(x) == find(y);
}


// 测试案例
int main() {
    ArrayGraph graph;

    // 1. 添加顶点（A、B、C、D、E、F、G、H、I）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');
    graph.addVertex('H');
    graph.addVertex('I');

    // 2. 添加边（有权无向图）
    graph.addEdge('A','B',3);
    graph.addEdge('A','C',1);
    graph.addEdge('A','D',2);

    graph.addEdge('B','A',3);
    graph.addEdge('B','D',2);

    graph.addEdge('C','A',1);
    graph.addEdge('C','D',2);
    graph.addEdge('C','F',2);

    graph.addEdge('D','A',2);
    graph.addEdge('D','B',2);
    graph.addEdge('D','C',2);
    graph.addEdge('D','E',2);

    graph.addEdge('E','D',2);
    graph.addEdge('E','F',4);

    graph.addEdge('F','C',2);
    graph.addEdge('F','E',4);
    graph.addEdge('F','G',3);

    graph.addEdge('G','F',3);

    graph.addEdge('H','I',3);
    graph.addEdge('I','H',3);

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 初始化
    parent.resize(graph.vertexNum);
    ranks.resize(graph.vertexNum, 1); // 初始秩均为1
    for (int i = 0; i < graph.vertexNum; i++) {
        parent[i] = i; // 初始父节点为自身，自成集合
    }

    // 5. 合并操作
    for(int i=0;i < graph.vertexNum;i++)
    {
        for(int j=0;j < graph.vertexNum;j++)
        {
            if(graph.graph[i][j]>NO_EDGE)
            {
                unite(i, j);
            }
        }
    }

    // 6. 判断连通性
    char start='A';
    char target='E';
    int startIndex = graph.findVertexIndex(start);
    int targetIndex = graph.findVertexIndex(target);
    cout << "父节点：";
    for(int i=0;i < graph.vertexNum;i++)
    {
        cout << parent[i] << " ";
    }
    cout << endl;
    cout << "    秩：";
    for(int i=0;i < graph.vertexNum;i++)
    {
        cout << ranks[i] << " ";
    }
    cout << endl;
    cout << "A和E是否连通：" << (same(startIndex,targetIndex) ? "是" : "否") << endl; // 是

    return 0;
}

输出结果


========= 带权邻接矩阵 ========
   A  B  C  D  E  F  G  H  I
A  0  3  1  2  0  0  0  0  0
B  3  0  0  2  0  0  0  0  0
C  1  0  0  2  0  2  0  0  0
D  2  2  2  0  2  0  0  0  0
E  0  0  0  2  0  4  0  0  0
F  0  0  2  0  4  0  3  0  0
G  0  0  0  0  0  3  0  0  0
H  0  0  0  0  0  0  0  0  3
I  0  0  0  0  0  0  0  3  0
========================
父节点：0 0 0 0 0 0 0 7 7
  秩：2 1 1 1 1 1 1 2 1
A和E是否连通：是

四、典型应用场景

并查集的核心是处理动态连通性，以下是最常见的应用：

图的连通分量统计：统计无向图中有多少个互不连通的连通分量；
Kruskal 算法求最小生成树：按边权排序后，用并查集判断边的两个端点是否连通，避免形成环，依次加入边直到所有节点连通；
分组问题：将元素按一定规则分组，判断两个元素是否在同一组，或合并两个组；
朋友圈问题（LeetCode 547）：判断社交网络中有多少个独立的朋友圈；
岛屿数量问题（进阶版）：动态添加陆地，实时查询岛屿数量；
等价类划分：根据等价关系（如相等、连通）将元素划分为若干等价类。

返回顶部